An Interior Gateway Protocol (IGP) is a type of protocol used for exchanging routing information between gateways (i.e., network devices) within a network including a set of commonly controlled gateways (e.g., a set of corporate local area networks); this network can be referred to as an autonomous system. The exchanged routing information can be used to forward data across the autonomous system using network-level protocols like the Internet Protocol (IP).
Specific examples of IGPs include open shortest path first (OSPF), intermediate system to intermediate system (IS-IS), and routing information protocol (RIP). IGPs are not responsible for routing or exchanging routing information outside of their respective autonomous systems. Exterior or border gateway protocols are used to exchange routing information between autonomous systems and rely on IGPs to resolve routes within an AS.
IS-IS protocol determines a set of paths from each network device in the autonomous system to each other network device in the autonomous system. A primary path is determined at each network device and the next hop to the destination is installed in the forwarding tables of the network device. However, in the case of failure of a next hope device or link a secondary or alternative path is also determined to be utilized in the case of failure until the network device can recalculate a primary path based on the changed topology of the network. RFC 5286 [Basic Specification for IP Fast Reroute: Loop Free Alternatives] lays out a method to compute Loop Free Alternatives (LFA) that is applicable to the intermediate system-intermediate system (IS-IS) protocol. RFC 5286 defines a set of criteria that a next hop must meet to be eligible and selected as a next hop for an LFA path.
Each time a node is encountered while calculating the shortest path tree (SPT) during the LFA computation, where the SPT is either rooted at the source node or at a neighbor node of the source node, all the link state protocol messages (LSPs) of that node are expanded and each inherits the next hop computed for that node (i.e. the source or neighbor node). This ‘inheriting’ process includes assigning the next hop of the node to all the unique prefixes advertised from this node. This expansion of the LSPs incurs cost not only to expand all the fragments of the LSP but more importantly to look up the reachable prefix in the local routing information base (local RIB) and ‘inherit’ the next hop of this node.